package com.ljx.offer;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;

/**
 * @author 李捷禧
 * Date: 2023/3/19
 * ClassName: C_52
 */

public class C_52 {

    @Test
    public void test(){
        ListNode headA = new ListNode(-1);
        ListNode res = headA;
        // 创建链表 1 2 3 4 5 6
        for (int i = 1; i < 7; i++) {
            res.next = new ListNode(i);
            res = res.next;
        }
        ListNode headB = new ListNode(-1);
        ListNode res2 = headB;
        // 创建链表 2 4 6
        for (int i = 1; i < 4; i++) {
           res2.next = new ListNode(i*2);
           res2 = res2.next;
        }



    }
    /**
     * 这个解法简单粗暴
     * 运行时间也少了很多
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) return null;
        ListNode node1 = headA, node2 = headB;

        // 明明最多只需要走一圈，加上两个链表不同的地方
        //我走过的路也是你够过得路，直到我们遇到一样的节点时，再结束这段艰难的路程
        //headA 1 3 5 6 8 9
        //headB 2 4 7 8 5 1
        //node1 ->1 3 5 6 8 9 -- 2 4 7 8 5 1 node2 ->2 4 7 8 5 1 -- 1 3 5 6 8 9
        //一直轮转，总有一次会相遇，遇不到就返回null
        while (node1 != node2) {
            node1 = node1 == null ? headB : node1.next;
            node2 = node2 == null ? headA : node2.next;
        }
        return node1;
    }

    /**
     * 利用hashset的不可重复性解决
     * 这个解答运行时间较长
     * @param headA
     * @param headB
     * @return
     */
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> res = new HashSet<>();
        //temp指向headA的链表头部
        ListNode temp = headA;
        //
        while(temp != null){
            res.add(temp);
            temp = temp.next;
        }
        //将headA的值都存在res中后，temp指向headB表头，
       // 再进行遍历，判断是否包含headB里面的元素，第一个相同的就输出
           temp = headB;
        while (temp != null){
            if(res.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
}
